/* 

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。



示例：
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
*/

/* 
思路：
*/

/**
 * @param {number} numRows
 * @return {number[][]}
 */
 var generate = function(numRows) {
    // 存储每行数组
    let ret=[]
    // 遍历行数
    for(let i=0;i<numRows;i++){
        // 声明行数对应的数组
        const arr=new Array(i+1).fill(1)
        // 每行从索引为1的项开始遍历
        for(let j=1;j<arr.length-1;j++){
            // 让当前行数的数组的第j项等于上一行的j-1和j的和
            arr[j]=ret[i-1][j-1]+ret[i-1][j]
        }
        ret.push(arr)
    }
    return ret
};

// 运行
let numRows = 5
console.log(generate(numRows));

/* 
时间复杂度：O(numRows^2)

空间复杂度：O(1)。不考虑返回值的空间占用。

*/
